package com.arithmeticEveryDay.blueBridge;

import java.util.Arrays;
import java.util.Scanner;

/*

        0   1   2   3   4   5   6   7
  w v   0   0   0   0   0   0   0   0
0(2,3)  0   0   3   3   6   6   9   9   
1(3,5)  0   0   3   5   5   8   10  10
2(4,6)  0   0   3   5   6   8   10  11
3(5,7)  0   0   3   5   6   8   10  11

dp[i][j]的含义：
剩余容量为j，可选物品为[0, j]情况下的最优解
方程为：dp[i][j] = max(dp[i-1][j] + value[i-1] + dp[i][j-weight[i-1])

7 4
2 3
3 5
4 6
5 7


 */
public class Main304 {
    int[] weight;
    int[] value;
    

    private Main304(int[] weight, int[] value) {
        super();
        this.weight = weight;
        this.value = value;
    }

    private int maxValue(int totalWeight) {
        int n = weight.length;
        int[][] dp = new int[n+1][totalWeight+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= totalWeight; j++) {
                if (j >= weight[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j], value[i-1] + dp[i][j-weight[i-1]]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        for (int i = 0; i <= n; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        
        return dp[n][totalWeight];
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int totalWeight = scan.nextInt();
        int n = scan.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        
        for (int i = 0; i < n; i++) {
            weight[i] = scan.nextInt();
            value[i] = scan.nextInt();
        }
        Main304 m = new Main304(weight, value);
        System.out.println(m.maxValue(totalWeight));
    }

}
